package wtx.leetcode;

import java.util.Arrays;
import java.util.Comparator;

/**
 * Hello world!
 */
public final class App {
  public int[][] merge(int[][] intervals) {
    if (intervals == null || intervals.length < 2) {
      return intervals;
    }

    Arrays.sort(intervals, new Comparator<int[]>() {
      @Override
      public int compare(int[] a, int[] b) {
        return Integer.compare(a[0], b[0]);
      }
    });

    int[][] ret = new int[intervals.length][2];
    int k = 0;
    for (int i = 0; i < intervals.length; ++i) {
      int j = i + 1;
      if (j >= intervals.length) {
        ret[k++] = intervals[i];
        break;
      }
      if (intervals[j][0] > intervals[i][1]) {
        ret[k++] = intervals[i];
      } else {
        int[] newPair = new int[2];
        newPair[0] = intervals[i][0];
        newPair[1] = Math.max(intervals[i][1], intervals[j][1]);
        intervals[j] = newPair;
      }
    }
    return Arrays.copyOfRange(ret, 0, k);
  }

  /**
   * Says hello to the world.
   * 
   * @param args
   *               The arguments of the program.
   */
  public static void main(String[] args) {
    App app = new App();
    int[][] intervals = {{1,3}, {8, 10}, {2, 6}, {12, 15}};
    // int[][] intervals = {{1,4}, {4, 5}};
    int[][] ret = app.merge(intervals);
    for (int i = 0; i < ret.length; ++i) {
      int[] pair = ret[i];
      System.out.println(String.format("[%d, %d],", pair[0], pair[1]));
    }
  }
}
